/**
 * Created by IntelliJ IDEA.
 * User: Alexander Fedulin
 * Date: 05.12.11
 * Time: 14:52
 * To change this template use File | Settings | File Templates.
 */

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Eggs {

    private String problem_input = "eggs.in";
    private String problem_output = "eggs.out";
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter out;

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    int n, k;
    int []a = new int[629];
    void load() throws IOException {
        n = nextInt();
        k = nextInt();
        for (int i = 0; i < n; i++)
        {
            a[i] = nextInt();
        }
    }
    long [][]dp = new long[520][520];
    final long inf = 1 << 34;

    long f(int n, int k)
    {
        if (k > n) return inf;
        if (k == 0) return 0;
        if (dp[n][k] != -1) return dp[n][k];
        if (n == k)
        {
            dp[n][k] = a[n - 1] + f(n - 1, k - 1);
            return dp[n][k];
        }
        dp[n][k] = a[n - 1] + f(n - 1, k - 1);
        for (int i = 1; i < n && n - i >= k; i++)
        {
            dp[n][k] = Math.min(a[n - i - 1] * (long)i + f(n - i, k), dp[n][k]);
        }
        return dp[n][k];
    }

    long solve() {
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= k; j++)
               dp[i][j] = -1;
        }
        Arrays.sort(a, 0, n);
        return f(n, k);
    }

    long solve2()
    {
        Arrays.sort(a, 0, n);
        long res = 0;
        for (int i = 0; i < n && k >= 0;)
        {
            int j = i;
            while (j < n && a[j] == a[i]) j++;
            int cnt = j - i;
            res += (long)(n - i - cnt + Math.min(k, cnt)) * (long)a[i];
            k -= Math.min(k, cnt);
            i = j;
        }
        return res;
    }

    void run() {
        try {
            boolean online_judge = System.getProperty("ONLINE_JUDGE") != null;
            if (online_judge) {
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            } else {
                br = new BufferedReader(new FileReader(problem_input));
                out = new PrintWriter(new FileWriter(problem_output));
            }
            int T = nextInt();
            for (int i = 0; i < T; i++)
            {
                load();
                out.println(Math.min(solve(), solve2()));
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(42);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public static void main(String args[]) {
        new Eggs().run();
    }
}
